""" dummy链表头的应用
快慢指针
栈 """

class ListNode:
     def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

""" 直觉解法，找到长度，在反推跳过元素 """
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        
    def get_length(head):
        length = 0 
        while head:
            length += 1
            head = head.next
        return length
    dummy = ListNode(0,head)
    length = get_length(head)
    cur = dummy
    for i in range(length-n):
        cur = cur.next
    cur.next = cur.next.next
    return dummy.next

""" 栈解法 """
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0, head)
    stack = list()
    cur = dummy
    while cur:
        stack.append(cur)
        cur = cur.next

    for i in range(n):
        stack.pop()
    
    prev = stack[-1]
    prev.next = prev.next.next
    return dummy.next

""" 快慢指针 快的和慢的相差n个步长"""
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0,head)
    fast = dummy
    slow = dummy

    for i in range(n): # 先走n步长
        fast = fast.next
    
    while fast.next: # fast 走到终点
        fast = fast.next
        slow = slow.next
    
    slow.next = slow.next.next # 剔除倒数n个元素
    return dummy.next